#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

// void test_2_wei_bag_problem1() {
//     vector<int> weight = {1, 3, 4};
//     vector<int> value = {15, 20, 30};
//     int bagweight = 4;

//     vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

//     // 不用初始化首列都是0，初始化首行就行了。
//     for (int j = weight[0]; j <= bagweight; j++) {
//         dp[0][j] = value[0];
//     }

//     // 开始循环遍历
//     for(int i = 1; i < weight.size(); i++) {
//         for(int j = 1; j <= bagweight; j++) {
//             if (j < weight[i]) dp[i][j] = dp[i - 1][j];
//             else dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]]+value[i]);
//         }
//     }
//     cout<<dp[weight.size()-1][bagweight]<<endl;
// }

// 复盘
    void test_2_wei_bag_problem1() {
        vector<int> weight = {3, 4, 3};
        vector<int> value = {1, 20, 15};
        int bagweight = 7;

        // 定义dp数组
        vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

        //dp数组初始化
        cout<<"物品： 0"<<endl;
        for (int j = weight[0]; j <= bagweight; j++) {
            dp[0][j] = value[0];
            cout<<"第 "<<j<<" 列 dp[0]["<<j<<"] = "<<dp[0][j]<<" ";
        }
        cout<<endl;

        // 开始遍历
        for(int i = 1; i < weight.size(); i++) {
            cout<<"物品: "<<i<<endl;
            for(int j = 1; j <= bagweight; j++) {
                if(j < weight[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
                cout<<j<<" ";
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<"背包的最大容量是：" <<bagweight<<" 共计物品的数量是: "<<weight.size()<<endl;
        cout<<"背包能装下的最大的价值是："<<dp[weight.size()-1][bagweight]<<endl;
        return;

    }

int main() {
   test_2_wei_bag_problem1();
}


